/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package insert;

import org.junit.Test;

import java.util.Arrays;

/**
 * <p>
 * 插入排序
 * </p>
 * @author LvJing
 * @version $Id:InsertSort.java v1.0 2018/7/21 上午9:16 LvJing Exp $
 */
public class InsertSort {

    /*
    介绍：插入排序的规则是每次插入一个元素到已排序好的数组中，根据已排序的数组，从后向前扫描可以知道该元素能落在数组的什么位置。
    逻辑判断为，当待排序元素大于已排序数组遍历到的元素，则证明待排序元素就放在当前遍历元素的后面；如果小于遍历到的元素，则证明
    应该放在该元素的前面，需要让这个元素后移。
     */

    public void insertSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1) {
            return;
        }

        //for (int i = 0; i < arr.length; i++) { 这里第一趟可以不用遍历，一个元素肯定有序
        for (int i = 1; i < arr.length; i++) {
            int j;
            int temp = arr[i];// 待排序元素
            for (j = i; j > 0 && temp < arr[j-1]; j--) {
                arr[j] = arr[j-1];// 待排序元素小于已排序元素，该元素需要后移
            }
            arr[j] = temp;
        }
    }

    @Test
    public void test() {
        int[] arr = {1, 3, 2, 6, 4, 8, 11, 5};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
